class Solution:
    def shortestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        length = len(s)
        for i in range(length):
            # if s[:length-i] == s[length-i-1::-1]:
            if s[:(length-i)//2] == s[length-i-1:(length-i-1)//2:-1]:
                break
        return s[:length-i-1:-1] + s


a = Solution()
print(a.shortestPalindrome("aacecaaa"))
print(a.shortestPalindrome("abcd"))
print(a.shortestPalindrome("aba"))
print(a.shortestPalindrome(""))
print(a.shortestPalindrome("a"))
